|
|
Algorithmic aspects of intersection representations
Chmel, Petr ; Jelínek, Vít (advisor) ; Kratochvíl, Jan (referee)
As some problems are (NP-)hard to solve in the general case, a possible approach is to try to solve the problem on a restricted class of graphs. In the thesis, we focus on graphs induced by axis-aligned L-shapes, so-called L-graphs, and a similar class of axis- aligned L-shapes and L-shapes, referred to as {L, L}-graphs, with two vertices sharing an edge if and only if their respective curves intersect. We show that recognizing both L- graphs and {L, L}-graphs is NP-complete. The second part of the thesis focuses on other typical decision problems on L-graphs and their relatives: finding the clique number, the independence number or a 3-coloring.
|
guest ::
